package com.bing.java.sort;

/**
 * 选择排序
 * 
 * 选择排序时间复杂度：O（n^2）
 * 
 * 
 * @author bing
 *
 *         2019年11月11日 上午11:25:14
 * 
 *         原理：选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。
 *         思路：1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置 2.再从剩余未排序元素中继续寻找最小（大）元素，
 *         然后放到已排序序列的末尾。3.重复第二步，直到所有元素均排序完毕。
 */
public class SortSelect {

	public static void main(String[] args) {
		int[] a = { 5, 3, 12, 8, 7 };
		int[] sortMaoPao = sortSelect(a);
		for (int i = 0; i < sortMaoPao.length; i++) {
			System.out.println(sortMaoPao[i]);
		}
	}

	public static int[] sortSelect(int[] a) {
		for (int i = 0; i < a.length - 1; i++) {
			// 最小索引
			int k = i;
			for (int j = k + 1; j < a.length; j++) {
				if (a[j] < a[k]) {
					k = j;
					;
				}
			}
			if (i != k) {
				int temp = a[i];
				a[i] = a[k];
				a[k] = temp;
			}
		}
		return a;

	}
}
